﻿using System;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Linq;
using StyleCop.CSharp;

namespace Jsl.StyleCop.CSharp
{
    /// <summary>
    /// A helper utility for working with code graphs.
    /// </summary>
    public static class CodeUnitGraphHelper
    {
        #region Public Methods
        /// <summary>
        /// Searches the code paths.
        /// </summary>
        /// <param name="graph">The graph.</param>
        /// <param name="start">The start.</param>
        /// <param name="visitCodeUnit">The visit code unit.</param>
        /// <returns>The search state.</returns>
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA2204:Literals should be spelled correctly", MessageId = "GraphSearchState", Justification = "That's the name.")]
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1011:ConsiderPassingBaseTypesAsParameters", Justification = "CodeUnitGraph is a better name than the whole type name.")]
        public static GraphSearchState SearchChildCodePaths(
            this CodeUnitGraph graph,
            ICodeUnit start,
            Func<ICodeUnit, GraphSearchState> visitCodeUnit)
        {
            if (graph == null)
            {
                throw new ArgumentNullException("graph");
            }

            if (visitCodeUnit == null)
            {
                throw new ArgumentNullException("visitCodeUnit");
            }

            var visitedVertices = new Stack<ICodeUnit>();
            var hashVisitedVertices = new HashSet<ICodeUnit>();
            var searchingChildren = true;
            var childrenEnumerators = new Stack<IEnumerator<ICodeUnit>>();
            var outEdges = graph.OutEdges(start);
            Contract.Assume(outEdges != null);
            childrenEnumerators.Push(outEdges.Select(edge => edge.Target).GetEnumerator());
            var currentCodeUnit = start;
            var state = GraphSearchState.ContinuePath;

            while (true)
            {
                if (searchingChildren)
                {
                    if ((state != GraphSearchState.ContinuePath)
                        && (state != GraphSearchState.HitEarlierItem))
                    {
                        // We should never get anything but the above states. SearchCodePaths changes StopPath and
                        // HitEarlierItem states into ContinuePath.
                        throw new InvalidOperationException();
                    }

                    var enumerator = childrenEnumerators.Peek();
                    if (enumerator.MoveNext())
                    {
                        // Process this code unit.
                        currentCodeUnit = enumerator.Current;
                        searchingChildren = false;
                    }
                    else
                    {
                        // Done with this, so fall back to the previous one.
                        childrenEnumerators.Pop();
                        if (childrenEnumerators.Count == 0)
                        {
                            return state;
                        }

                        currentCodeUnit = visitedVertices.Pop();
                    }

                    state = GraphSearchState.ContinuePath;
                }
                else
                {
                    if (hashVisitedVertices.Contains(currentCodeUnit))
                    {
                        // If we have looped back on ourselves and hit a code unit we already looked at.
                        state = GraphSearchState.HitEarlierItem;
                        searchingChildren = true;
                    }
                    else
                    {
                        visitedVertices.Push(currentCodeUnit);
                        hashVisitedVertices.Add(currentCodeUnit);

                        // Visit the code unit.
                        state = visitCodeUnit(currentCodeUnit);
                        switch (state)
                        {
                            case GraphSearchState.ContinuePath:
                                // Search the child code paths.
                                childrenEnumerators.Push(graph.OutEdges(currentCodeUnit).Select(edge => edge.Target).GetEnumerator());
                                searchingChildren = true;
                                break;

                            case GraphSearchState.Found:
                                // Stop searching and return we found what we were looking for.
                                return GraphSearchState.Found;

                            case GraphSearchState.NotFound:
                                // Stop searching and return that the thing we are searching for can't be found.
                                return GraphSearchState.NotFound;

                            case GraphSearchState.StopPath:
                                // One of the children flagged that we should stop this path. Since we came back to here, we can
                                // just continue since we are past the path that StopPath was returned from.
                                currentCodeUnit = visitedVertices.Pop();
                                state = GraphSearchState.ContinuePath;
                                searchingChildren = true;
                                break;

                            case GraphSearchState.HitEarlierItem:
                                // We circled back on ourselves so continue with the next path.
                                state = GraphSearchState.ContinuePath;
                                break;

                            default:
                                throw new InvalidOperationException("The GraphSearchState is invalid.");
                        }
                    }
                }
            }
        }
        #endregion Public Methods
    }
}